package exercises.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/">
 * 5897. 将数组分成两个数组并最小化数组和的差</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
 * <p>
 * 请你返回 最小 的数组和之差。
 *
 * @author or2
 * @date 2021年10月10日 时间: 16:33
 */
public class No5897 {
    public int minimumDifference(int[] nums) {
        Arrays.sort(nums);
        int bound = binarySearchBounds(nums);

        int auxiliary1 = 0, auxiliary2 = 0,
                bigIndex = nums.length - 1, lowerIndex = 0,
                size1 = 0, size2 = 0;
        for (int i = 0, num, numsLength = nums.length; i < numsLength; i++) {
            if (lowerIndex < bound && bound <= bigIndex)
                num = -nums[lowerIndex] > nums[bigIndex] ? nums[lowerIndex++] : nums[bigIndex--];
            else if (lowerIndex < bound)
                num = nums[lowerIndex++];
            else
                num = nums[bigIndex--];

            if (num < 0)
                if (size2 * 2 > numsLength || auxiliary1 > auxiliary2 && size1 * 2 != numsLength) {
                    auxiliary1 += num;
                    size1++;
                } else {
                    auxiliary2 += num;
                    size2++;
                }
            else {
                if (size2 * 2 > numsLength || auxiliary1 < auxiliary2 && size1 * 2 != numsLength)
                    auxiliary1 += num;
                else {
                    auxiliary2 += num;
                    size2++;
                }
            }
        }

        return Math.abs(auxiliary1 - auxiliary2);
    }

    private int binarySearchBounds(int[] nums) {
        int length = nums.length,
                left = 0, right = length, mid = -1;
        if (nums[0] > 0)
            return 0;

        while (left < length) {
            mid = left + (right - left >> 1);
            if (nums[mid] >= 0)
                if (nums[mid - 1] < 0)
                    return mid;
                else
                    right = mid;
            else
                left = mid + 1;
        }

        return left;
    }

    //————————————————————————————————————————————————————————————————————————————————————————————————————————

    private int totalLen, cnt, goal, ans = 0x7fffffff;
    private Aux[] aux;

    private static class Aux {
        int value;
        byte freq;

        public Aux(int value, byte freq) {
            this.value = value;
            this.freq = freq;
        }
    }

    public int minimumDifference2(int[] nums) {
        totalLen = nums.length;
        aux = new Aux[1 << totalLen / 2 + 1];
        cnt = 0;
        int sum = 0;
        for (int num : nums) sum += num;
        goal = sum >> 1;

        dfs1(nums, 0, 0, (byte) 0);
        Arrays.sort(aux, 0, cnt, ((o1, o2) -> o1.value - o2.value));

        dfs2(nums, totalLen + 1 >> 1, 0, (byte) 0);
        return ans * 2 + Math.abs(sum - goal * 2);
    }

    void dfs1(int[] nums, int index, int value, byte amount) {
        if (amount == totalLen >> 1 || index == totalLen >> 1) {
            aux[cnt++] = new Aux(value, amount);
            return;
        }

        dfs1(nums, index + 1, value, amount);
        dfs1(nums, index + 1, value + nums[index], (byte) (amount + 1));
    }

    void dfs2(int[] nums, int index, int value, byte amount) {
        if (amount == totalLen >> 1 || index == totalLen) {
            int left = 0, right = cnt;
            while (left < right) {
                int mid = left + (right - left >> 1);
                if (aux[mid].value + value <= goal) left = mid + 1;
                else right = mid;
            }

            int pLeft = right - 1, condition = totalLen >> 1;
            while (pLeft >= 0 && aux[pLeft].freq + amount != condition) pLeft--;
            if (pLeft >= 0)
                ans = Math.min(ans, Math.abs(aux[pLeft].value + value - goal));

            while (right < cnt && aux[right].freq + amount != condition) right++;
            if (right < cnt)
                ans = Math.min(ans, Math.abs(aux[right].value + value - goal));

            return;
        }

        dfs2(nums, index + 1, value, amount);
        dfs2(nums, index + 1, value + nums[index], (byte) (amount + 1));
    }

    //——————————————————————————————————————————————————————————————————————————————————————————————————————

    private int sum;
    public int minimumDifference3(int[] nums) {
        totalLen = nums.length;
        cnt = 0;
        int sum = 0;
        for (int num : nums) sum += num;
        this.sum = sum;
        goal = sum >> 1;

        dfs3(nums, 0, 0, (byte) 0);

        return ans;
    }

    void dfs3(int[] nums, int index, int value, byte amount) {
        if (index == totalLen)
            return;
        if (amount == totalLen >> 1) {
            ans = Math.min(ans, Math.abs(value - goal) + Math.abs(sum - value - goal));
            return;
        }

        dfs3(nums, index + 1, value, amount);
        dfs3(nums, index + 1, value + nums[index], (byte) (amount + 1));
    }
}
